package leetcode_周赛._2023._11;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 第 370 场周赛
 * AC_2
 *
 * @author yezh
 * @date 2023/11/5 19:49
 */
public class _05 {

    /**
     * 找到冠军 II
     * 算法: 模拟
     */
    public int findChampion(int n, int[][] edges) {
        boolean[] vis = new boolean[n];
        for (int[] edge : edges) vis[edge[1]] = true;
        int ans = -1;
        for (int i = 0; i < n; i++)
            if (!vis[i]) {
                if (ans != -1) return -1;
                ans = i;
            }
        return ans;
    }

    /**
     * 在树上执行操作以后得到的最大分数 <p />
     * 算法: 正难则反 <p />
     * 遍历节点, 如果损失节点, 则其所有的子节点都可以拿到; 如果不损失节点, 继续往下遍历 <br />
     * 遍历到叶子节点, 表示叶子节点的上面节点都没有损失, 则叶子节点肯定要损失 <br />
     * 如果 x 为叶子节点, 则 g[x].size() = 1, 表示只有一条边 <br />
     */
    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] edge : edges) {
            g[edge[0]].add(edge[1]);
            g[edge[1]].add(edge[0]);
        }
        long ans = 0;
        for (int val : values) ans += val;
        // 防止 0 被当作叶子节点
        g[0].add(-1);
        return ans - dfs(0, -1, g, values);
    }

    long dfs(int x, int fa, List<Integer>[] g, int[] values) {
        if (g[x].size() == 1) return values[x];
        long lose = 0;
        for (Integer c : g[x])
            // 只要 c != fa, 就不会向上遍历, 因为这是一棵合法的树, 不会出现环
            if (c != fa) lose += dfs(c, x, g, values);
        return Math.min(values[x], lose);
    }

}
